package leetcode.code0576;

import leetcode.IDebug;

public class Solution implements IDebug {
	int mod = (int) 1e9 + 7;

	public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
		Integer[][][] dp = new Integer[m][n][maxMove + 1];
		return this.findPaths(m, n, maxMove, startRow, startColumn, dp);
	}

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	private int findPaths(int m, int n, int maxMove, int startRow, int startColumn, Integer[][][] dp) {
		if (maxMove < 0) {
			return 0;
		}
		if (startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) {
			return 1;
		}
		if (dp[startRow][startColumn][maxMove] != null) {
			return dp[startRow][startColumn][maxMove];
		}
		int ans = 0;
		for (int i = 0; i < 8; i += 2) {
			int nextx = d[i] + startRow, nexty = d[i + 1] + startColumn;
			ans += this.findPaths(m, n, maxMove - 1, nextx, nexty, dp);
			ans %= mod;
		}
		dp[startRow][startColumn][maxMove] = ans;
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
